#ifndef LEETCODE_CN_CPP_PROBLEMS_300_H
#define LEETCODE_CN_CPP_PROBLEMS_300_H

#include <algorithm>
#include <vector>

using namespace std;

namespace problem_300
{

class Solution
{
public:
    int lengthOfLISUnoptimized(vector<int> &nums)
    {
        if (nums.empty())
        {
            return 0;
        }
        int n = nums.size();
        vector<int> lengths(n, 0);
        for (int i = 0; i < n; ++i)
        {
            int len = 0;
            for (int j = i - 1; j >= 0; --j)
            {
                if (nums[j] < nums[i])
                {
                    len = max(len, lengths[j]);
                }
            }
            lengths[i] = len + 1;
        }
        return *(max_element(lengths.begin(), lengths.end()));
    }

    // optimized
    int lengthOfLIS(vector<int> &nums)
    {
        if (nums.empty())
        {
            return 0;
        }
        /**
         * 贪心，保持同一长度的串的末尾数字永远为最小的
         */
        int n = nums.size();
        vector<int> smallestAtLen;
        smallestAtLen.reserve(n);
        smallestAtLen.push_back(nums.front());
        for (int i = 1; i < nums.size(); ++i)
        {
            auto n = nums[i];
            if (n > smallestAtLen.back())
            {
                smallestAtLen.push_back(n);
                continue;
            }
            auto index = distance(
                smallestAtLen.begin(),
                lower_bound(smallestAtLen.begin(), smallestAtLen.end(), n));
            smallestAtLen[index] = n;
        }
        return smallestAtLen.size();
    }
};

} // namespace problem_300

#endif //LEETCODE_CN_CPP_PROBLEMS_300_H
